package TenkindsOfAlgorithm.dynamicProgramming;

/**
 * 给定的数组 : arr = {1,2,4,1,7,8,3}
 * 从数组中取值要求不能相邻，求一个最大值（打家劫舍问题）
 * 分析：https://www.bilibili.com/video/BV12W411v7rd/?spm_id_from=333.788.recommend_more_video.-1
 * 这是一个递归的过程，设opt为最优解,opt分为二种情况{
 *     1) 选择当前值 并选择opt(i-2)
 *     2)不选当前值  ==> opt(i-1)
 * }
 *
 *
 * part2 引出问题：使用递归会产生很多overlap问题 opt(3)要求2次and more
 * 区别在于 for循环做时间复杂度为n，一个如同二叉树，时间复杂度n^2
 */
class Question1 {
    public static void main(String[] args) {
        int[] arr ={1, 2, 4, 1, 7, 8};
        int dp = dp_rec(arr, arr.length - 1);
        System.out.println(dp);
        int dp_opt = dp_opt(arr, arr.length - 1);
        System.out.println(dp_opt);
    }
    public static int  dp_rec(int []arr,int i){
        // 只有一个数据的情况下
        if (i==0){
            return arr[0];
        }else if (i==1){
            return Math.max(arr[0],arr[1]);
        }else {
            return Math.max(dp_rec(arr,i-1),dp_rec(arr,i-2)+arr[i]);
        }
    }
    public static int dp_opt(int []arr,int i){
        // 使用temp存放最优解
        int [] temp = new int[arr.length];
         temp[0] = arr[0];
         temp[1] = Math.max(arr[1],arr[0]);
        for (int j = 2; j < arr.length; j++) {
            int A =arr[j]+temp[j-2];
            int B =temp[j-1];
            temp[j] = Math.max(A,B);
        }
        return temp[temp.length-1];
    }
}
